'''
@Author: shj
@Date: 2019-03-22 11:24:21
@LastEditTime: 2020-06-01 19:23:13
@LastEditors: shj
@Description:  插入排序算法(直接插入，二分插入)
@FilePath: /python3/algorithms/insert_sort.py
'''
"""
插入排序算法

1、将第一个元素认为已经被排序，形成初始有序队列
2、取出未排序队列的第一个元素记为标记元素，在已经排序的元素序列中从后向前扫描
3、若标记元素小于有序队列中的比较元素，将有序队列中的比较元素及其右段整体右移一位
（标记元素与比较元素相等，不必右移，使用上次移动的元素位置）
5、将新元素插入到该位置后
6、重复步骤2~5

最坏时间复杂度	O(n^{2})
最优时间复杂度	O(n)
平均时间复杂度	O(n^{2})
最坏空间复杂度	总共  O(n) ，需要辅助空间 O(1)
"""


# 简单插入排序
def insert_sort(sort_list):
    """sort by inserted for list"""
    length = len(sort_list)

    # 长度小于1,不必排序
    if length <= 1:
        return sort_list
    # 默认第一个元素已排序，从第二个元素开始为未排序序列
    for i in range(1, length):  # 取第一个未排序元素
        key = sort_list[i]  # 暂存标记元素
        j = i - 1  # 需要移动的元素位置
        # 标记元素与已排序元素进行比较
        # 在有效序列中（j >= 0），若标记元素小于某个元素，将这一段元素整体后移
        # 注意：不要用冒泡移位的方法[(a, b) = (b, a)]，太耗时
        while j >= 0 and key < sort_list[j]:  # 移动元素
            sort_list[j + 1] = sort_list[j]
            j -= 1
        # 插入元素
        sort_list[j + 1] = key
    return sort_list


# 二分插入排序要点
# 因为前段有序，所以可以在比较时用二分法，节省时间
def binary_insert_sort(list):
    length = len(list)  # 序列长
    if length <= 1:  # 预处理
        return list
    for i in range(1, length):
        key = list[i]  # 标记元素
        # 低位，高位，插入位置
        low, high, flag = 0, i - 1, None
        while low <= high:  # 比较结束
            mid = low + (high - low) // 2
            # 标记元素等于比较元素，直接找到插入位置，提前停止
            if key == list[mid]:
                flag = mid
                break
            # 标记元素小于中值，插入位置在左段
            if key < list[mid]:
                high = mid - 1
            # 标记元素大于中值，插入位置在右段
            else:
                low = mid + 1
        # 提前终止比较，对插入位赋值
        if flag is None:
            '''
            重点注意：
            插入位置只能为低位（low），因为高位（high）插入会越界（插入段后移）
            '''
            flag = low
        # 后移插入位置段
        j = i - 1
        while j >= flag:
            list[j + 1] = list[j]
            j -= 1
        # 插入元素
        list[flag] = key

    return list
